/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package ua.yandex.prioritymap;

import java.util.Iterator;
import java.util.Map;

/**
 *
 * @author Mitya
 */
public class PriorityHashMap<K, V> implements Iterable<Map.Entry<K, V>> {

    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public static final int DEFAULT_INITAL_CAPACITY = 16;

    int treshold;
    Entry<K, V>[] buckets;
    Heap<K> heap;
    final float loadFactor;
    int size;

    public PriorityHashMap(int initialCapacity, float loadFactor) {

        this.loadFactor = loadFactor;

        int capacity = 1;
        while (capacity < initialCapacity) {
            capacity = capacity << 1;
        }
        treshold = (int) (capacity * loadFactor);
        buckets = new Entry[capacity];
        heap = new Heap();
    }

    public PriorityHashMap(int initialCapacity) {

        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public PriorityHashMap() {

        this(DEFAULT_INITAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public void put(K key, V value) {

        int hash = hash(key.hashCode());
        int i = indexFor(hash, buckets.length);

        if (get(key) == null) {
            heap.insert(key);
        }

        for (Entry<K, V> elem = buckets[i]; elem != null; elem = elem.next) {
            Object k;
            if (elem.hash == hash && (elem.key.equals(key))) {
                V oldValue = elem.value;
                elem.value = value;
                return;
            }
        }

        addEntry(hash, key, value, i);
    }

    public V get(K key) {

        int hash = hash(key.hashCode());
        for (Entry<K, V> e = buckets[indexFor(hash, buckets.length)];
                e != null;
                e = e.next) {
            if (e.hash == hash && (e.key == key || key.equals(e))) {
                return e.value;
            }
        }
        return null;
    }

    public V peekValueWithPriorityKey() {
        K key = heap.max();
        V value = get(key);
        return value;
    }

    public V pollValueWithPriorityKey() {
        K key = heap.delMax();
        V value = remove(key);
        return value;
    }

    private V remove(Object key) {
        Entry<K, V> newElement = removeEntryForKey(key);
        return (newElement == null ? null : newElement.value);
    }

    private Entry<K, V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, buckets.length);
        Entry<K, V> prev = buckets[i];
        Entry<K, V> e = prev;

        while (e != null) {
            Entry<K, V> next = e.next;
            Object k;
            if (e.hash == hash
                    && ((k = e.key) == key || (key != null && key.equals(k)))) {
                size--;
                if (prev == e) {
                    buckets[i] = next;
                } else {
                    prev.next = next;
                }
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

    private void resize(int newCapacity) {
        Entry[] oldBuckets = buckets;
        int oldCapacity = oldBuckets.length;

        Entry[] newBuckets = new Entry[newCapacity];
        copyTo(newBuckets);
        buckets = newBuckets;
        treshold = (int) (newCapacity * loadFactor);
    }

    private void copyTo(Entry[] newBuckets) {
        Entry[] src = buckets;
        int newCapacity = newBuckets.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K, V> newEntry = src[j];
            if (newEntry != null) {
                src[j] = null;
                do {
                    Entry<K, V> nextEntry = newEntry.next;
                    int i = indexFor(newEntry.hash, newCapacity);
                    newEntry.next = buckets[i];
                    newEntry = nextEntry;
                } while (newEntry != null);

            }
        }

    }

    private void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K, V> newEntry = buckets[bucketIndex];
        buckets[bucketIndex] = new Entry<>(hash, key, value, newEntry);
        if (size++ >= treshold) {
            resize(2 * buckets.length);
        };
    }

    static class Entry<K, V> implements Map.Entry<K, V> {

        final K key;
        V value;
        Entry<K, V> next;
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K, V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        @Override
        public final K getKey() {
            return key;
        }

        @Override
        public final V getValue() {
            return value;
        }

        @Override
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        @Override
        public String toString() {
            return "[" + key.toString() + ", " + value.toString() + "]";
        }
    }

    Iterator entrySet() {
        return new HashIterator();
    }

    class HashIterator implements Iterator {

        Entry<K, V> next;        // next entry to return
        int index;              // current slot
        Entry<K, V> current;     // current entry
        Iterator heapIterator;

        HashIterator() {
            heapIterator = heap.iterator();
        }

        @Override
        public final boolean hasNext() {
            return heapIterator.hasNext();
        }

        @Override
        public Entry<K, V> next() {
            K key = (K) heapIterator.next();
            V value = PriorityHashMap.this.get(key);

            return new Entry<K, V>(key.hashCode(), key, value, null);

        }

        @Override
        public void remove() {
        }

    }

    @Override
    public Iterator<Map.Entry<K, V>> iterator() {
        return new HashIterator();
    }

    private static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    private static int indexFor(int h, int length) {
        return h & (length - 1);
    }

}
